package com.other;

import java.util.HashMap;
import java.util.Map;

//定义双向链表类
class LinkNode{
    int key;
    int value;
    LinkNode pre;
    LinkNode next;

    public LinkNode(){

    }
    public LinkNode(int key,int value){
        this.key = key;
        this.value = value;
    }
}
public class LRUCache {
    int capacity;
    Map<Integer,LinkNode> map = new HashMap<>();
    LinkNode head = new LinkNode(0,0);
    LinkNode tail = new LinkNode(0,0);
    public LRUCache(int capacity) {
        //初始化构造
        this.capacity = capacity;
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        if (map.containsKey(key)){
            LinkNode node = map.get(key);
            removeNodeToHead(node);
            return node.value;
        }else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (!map.containsKey(key)){
            if (map.size()==capacity){
                LinkNode del = tail.pre;
                map.remove(del.key);
                delNode(del);
            }
            //插入到头部
            LinkNode newNode = new LinkNode(key,value);
            LinkNode temp = head.next;
            head.next = newNode;
            newNode.pre = head;
            newNode.next = temp;
            temp.pre = newNode;
            //map存储
            map.put(key,newNode);
        }else {
            LinkNode node = map.get(key);
            removeNodeToHead(node);
            node.value = value;
            //更新map
            map.put(node.key,node);
        }
    }
    //删除链表节点
    private void delNode(LinkNode node){
        if (node==null){
            return;
        }
        LinkNode pre = node.pre;
        LinkNode next = node.next;
        pre.next = next;
        next.pre = pre;
    }
    //移动链表节点到头部
    private void removeNodeToHead(LinkNode node){
        if (node==null){
            return;
        }
        delNode(node);
        LinkNode next = head.next;
        head.next = node;
        node.pre = head;
        node.next = next;
        next.pre = node;
    }
}